package intersect_intervals;

require Exporter;
use strict;
use warnings;


our @ISA = qw(Exporter);
our $VERSION = 1.00;
our @EXPORT = qw(	
					intersect_intervals
				);


#-----------------------------------------------------------------------------------------
#
#	lower_bound
#
#		returns the position of the next item in an array 
#				which is greater than the test value
#
#		array items are themselves arrays, and the value which is being compared
#				is specified in index.
#
#		Thus lower_bound(@values, 15, 2) finds the first tuple in @values whose 2nd
#				member is greater than 15
#
#				e.g. for @values[3] [ [0, 0, 3], [0, 0, 4],  [0, 0, 13], [0, 0, 15], [0, 0, 19] ]
#					lower_bound(@values, 15, 2) gives 3						
#	
#
#-----------------------------------------------------------------------------------------
sub lower_bound(\@$$)
{
	my ($val, $test,$index) = @_;
	my $first = 0;
	my $last = @$val;
	my $len = $last - $first;
	my $mid;
	while ($len > 0)
	{
		my $half = int ($len / 2);
		$mid = $first + $half;
		if ($val->[$mid][$index] < $test)
		{
			$first = $mid + 1;
			$len = $len - $half - 1
		}
		else
		{
			$len = $half
		}
	}
	return $first;
}


#88888888888888888888888888888888888888888888888888888888888888888888888888888888888888888
#
#	intersect_intervals
#
#		test whether a specified interval overlaps with an array of intervals
#
#
#		@array: an array of inclusive intervals [beg, end]
#				Sorted by the start e.g. @array = sort{$a->[0] <=> $b->[0]} @array
#				Arrays are non-overlapping
#
#		$t1, $t2: begin and end of test interval
#
#
#
#88888888888888888888888888888888888888888888888888888888888888888888888888888888888888888
sub intersect_intervals(\@$$)
{
	my ($val, $t1,  $t2) = @_;
	# make sure right way around
	($t1, $t2) = ($t2, $t1) if $t2 < $t1;
	{
		my $pos = lower_bound(@$val, $t1, 1);

		# all intervals greater than test interval
		return -1 if ($pos == @$val);

	#	print "\n$pos\t$val->[$pos][0]\t$val->[$pos][1]\t$t1\t$t2\n";
		# interval at $pos contains beginning of test interval
		return $pos if ($t2 >= $val->[$pos][1]) || ($t1 >= $val->[$pos][0]);
	}

	{
		my $pos = lower_bound(@$val, $t1, 0);
		
		# all intervals greater than test interval
		return -1 if ($pos == @$val);
	
		# interval at $pos contains beginning of test interval
		return $pos if ($t2 >= $val->[$pos][0]);
	}

	
	return -1;
}

1;
